1. Field of the Invention
The invention relates generally to the field of fault identification and analysis in computer software. More particularly, the invention relates to a method and apparatus used for the automatic analysis of computer software.
2. Background of the Invention
Since the day the first computer program was written and to this day, errors or faults in computer software are an expected and commonplace occurrence. Even though such faults are expected, fault identification and analysis is a problem which has forever plagued programmers. This due in part, to the fact that the fault rate for a carefully constructed program can be about 5 faults per 1,000 lines of source code so that a one million-line program may contain 5,000 faults! Compound this with the fact that computer software faults are different from computer hardware faults in that the software faults do not obey the same simplified rules of proximity of cause and effect. That is to say, a computer software fault does not necessarily have to appear close to its failure, but instead can be located almost anywhere within a much larger software system. Therefore, even when a fault is known to exist, determining the origin and location of that fault is extremely difficult at best.
3. Description of the Prior Art
As a result of the above mentioned characteristics of computer software, the prior art has developed a number of methods and apparatus to assist a programmer in the development and analysis of software. The methods and apparatus of the prior art encompass a wide array of systems and techniques, each generally applicable to a different period of the overall computer software development process. Among these prior art methods and apparatus are: 1) structured design techniques; 2) language-sensitive development tools; 3) highly-efficient and informative language interpreters and compilers; and 4) an assortment of program profilers and debuggers and emulators which assist in identifying and locating faults in software during the debugging and testing of the software. Despite all these tools, techniques and related efforts, a large amount of programmer time is spent in trying to understand how a program works and many failures are tolerated out of fear of further "breaking" a software system.
There are many problems associated with existing tools and techniques for identifying and locating faults in computer software. Traditionally, a programmer had to debug or analyze a program through the use of some kind of "hook" or output statement which was part of the programming language used for the software program. For example, in one particular language a "PRINT" statement would be inserted by a programer into one or more locations of a program being analyzed so that upon encountering the PRINT statement, the program being analyzed would output to an appropriate output device the contents of some registers, variables, etc. In this manner, the programer would examine the output of the executed PRINT statement searching for clues as to why the program failed. Needless to say, this method of program analysis and debugging is very tedious for the programmer and error prone as well.
Another method of program debugging and analysis involves the use of a special program, known as a program debugger which monitors the execution of a software program and oversees its execution. Such debuggers typically offer enhanced flexibility and more information to the programmer than possible with the simple PRINT method, particularly with respect to a user interface presented to the programmer. Utilizing a debugger, a programer will normally specify one or more lines of the software program as "breakpoints", or points within a software program which when encountered suspend the execution of the program so that the programmer may examine processor registers or program variables. Breakpoints are not limited to specific lines of code, breakpoints may be used to interrupt execution when an expression changes value, or when a expression reaches a value. Despite apparent advantages over the PRINT method, program debugging and analysis using known tools suffer from many of the same infirmities i.e., they do not automate the understanding of cause-effect relationship between faults and failures (manifestation of fault).
The first problem associated with these above mentioned debugging and analysis methods and tools is where to begin. This is largely a hit or miss proposition for the programmer. Therefore, the programmer will typically insert a number of breakpoints or PRINT statements which are scattered throughout the program under test. As the programmer narrows down his understanding of the nature and location of program fault(s) responsible for a failure, unnecessary breakpoints or PRINT statements are normally removed or deactivated. This technique of randomly inserting breakpoints or PRINT statements throughout a program is highly inefficient, time-consuming, and error-prone.
Second, even if the programmer has some idea where within a program to place a breakpoint, the programmer must determine what to examine at that location. That is, a particular section of a program may use a large number of variables, registers or memory locations, thereby making the programmer's job of identifying the fault(s) more difficult. While debuggers and analyzers have certainly facilitated the examination of variables, registers or memory locations, they have by no means eliminated the problem of making a decision as to what variables, memory, or registers to examine and when to examine them. Furthermore, debuggers do not help to decide what is the meaning of the value of a variable and what other variables of what other statements need to be examined until the fault statement is found. As can be appreciated, the traditional techniques and tools used for debugging or analyzing a software program is not highly automated.
In an attempt to overcome these stated deficiencies in the art of program debugging and analysis, the prior art has developed additional tools and techniques.
U.S. Pat. No. 4,853,851, "System For Determining The Code Coverage Of A Tested Program Based Upon Static And Dynamic Analysis Recordings" issued to Horsch on Aug. 1, 1989 teaches a system for analyzing programs by measuring the degree of code coverage of a program being tested during specific test phases. The system disclosed utilizes a static and dynamic instruction flow indicator which permits a determination of the test cover results by correlating the data of the static and dynamic instruction flow. In this manner, the number of untested statements can be determined during a test phase of a computer program.
Although the more statements covered during the test of a program the better, the fact that a statement was executed does not provide any information on the statement validity. In particular, the statement may have been constructed wrong; the statement may be executed at the wrong place at the wrong time; or the statement may not contribute to the observed result.
U.S. Pat. No. 4,802,116, "Programmed Controller" issued to Ward, et al on Jan. 31, 1989 teaches programmed controller which controls a machine process and facilitates its debugging. The application programs disclosed are specifically designed to simulate specific control schemes for sections of the machine by being organized into one or more separate loops. A built-in control mechanism records the states of these loops along with the conditions responsible for the transitions between those states. This teaching is limited in application to only those processes that are specially coded by very specific syntax rules as consisting of independent loops, where the means of tracing the states of these loops are pre-coded in the programs controlling the process.
A theoretical approach to the general problem of program analysis was disclosed by Thomas J. McCabe in the article "A Complexity Measure" published in IEEE Transactions on Software Engineering, Vol. Se-2, No. 4, December 1976, pp. 308-320. Cyclomatic Complexity was proposed in this article as a measure of program complexity. This measurement is nothing more than the number of independent passes within a subroutine. This complexity measurement is useful to promote the design of less sophisticated software routines which are also easier to test. However, counting the number of independent passes does not eliminate their necessity.
Despite these and other attempts made by the prior art, software debugging and analysis remains a difficult, time-consuming and error prone process. A critical shortcoming in the prior art is that there are no teachings for general methods or apparatus which are capable of automatically determining the location of logic faults in software programs even within a broad area of a program. This is due, in large part, to a general belief which exists in the art that such automation is not possible because software does not conform to the rules of proximate cause and effect and that a software program has no knowledge of what results are expected of it unless those expected results are pre-coded within the program. Such pre-coding is itself programming and therefore is also error-prone.
Therefore, a continuing need exists in the art for a method and apparatus which more highly automates the chore of software program debugging and analysis.